//
// Created by liushuai on 2021/1/4.
//

#include "longestPalindrome.h"
// no pass
using namespace std;

bool isPalindrome(string s) {
    if (s.size() == 1)
        return true;
    else {
        int head = 0;
        int tail = s.size() - 1;
        while (head <= tail) {
            if (s[head] == s[tail]) {
                tail--;
                head++;
            } else
                return false;
        }
        return true;
    }
}
std::pair<int, int> extentOfStr(string s, int start, int end) {
    while (start >= 0 && end < s.size() && s[start] == s[end]) {
        start--;
        end++;
    }
    return {start + 1, end - 1};
}
string longestPalindrome(string s) {
    int size = s.size();
    if (size == 0 || size == 1)
        return s;
    int left = 0;
    int right = 0;

    for (int start = 0; start < size; start++) {
        auto [left1, right1] = extentOfStr(s, start, start);
        auto [left2, right2] = extentOfStr(s, start, start + 1);
        if (right1 - left1 > right - left) {
            left = left1;
            right = right1;
        }
        if (right2 - left2 > right - left) {
            left = left2;
            right = right2;
        }
    }
    return s.substr(left, right - left + 1);
}

int longestPalindrome1(string s) {
    map<char, int> freq;
    int res = 0;
    int count_one = 0;
    for (auto ch : s) {
        if (freq.count(ch))
            freq[ch] += 1;
        else
            freq[ch] = 1;
    }
    for (auto e : freq) {
        if (e.second % 2 == 0)
            res += e.second;
        else {
            res += e.second - 1;
        }
    }
    return s.size() != res ? res + 1 : res;
}
